package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

/**
 * 剑指offer
 * 数字在升序数组中出现的次数
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：494000
 * 本题知识点： 数组 二分
 * 算法知识视频讲解
 * 题目描述
 * 统计一个数字在升序数组中出现的次数。
 * 示例1
 * 输入
 * 复制
 * [1,2,3,3,3,3,4,5],3
 * 返回值
 * 复制
 * 4
 */
public class GetNumberOfK {

    @Test
    public void test() {
        System.out.println(GetNumberOfK(new int[]{3}, 3));
    }

    // 思路： 先使用二分查找找到第一个k，然后遍历他的左边和右边找到其余的k
    public int GetNumberOfK(int[] array, int k) {

        if (array.length == 0 || k < array[0] || k > array[array.length - 1]) {
            return 0;
        }

        // 二分查找
        int left = 0;
        int right = array.length - 1;
        int mid = (left + right) / 2;

        boolean flag = false;

        while (left <= right) { // 二分查找这里一定要写小于等于，因为这样才能在数组长度为1的数组上做二分查找。
            if (array[mid] == k) {
                flag = true;
                break;
            } else if (array[mid] > k) {
                left = mid + 1;
                mid = (left + right) / 2;
            } else {
                right = mid - 1;
                mid = (left + right) / 2;
            }
        }

        if (!flag) return 0;

        right = mid + 1; // 遍历右边找k的个数
        left = mid - 1; // 遍历左边找k的个数
        int result = 1;

        while (left >= 0 && array[left--] == k) { // 碰到数组边界问题， 一定要先判定下表是否越界
            result++;
        }

        while (right < array.length && array[right++] == k) {
            result++;
        }

        return result;
    }
}
